Dưới thời Pháp thuộc, ban đầu tuyến đường chỉ bao gồm đoạn từ đường An Bình đến nhà thờ Cha Tam hiện nay, khi đó là đường đô thị thuộc thành phố Chợ Lớn với tên gọi rue des Marins (đường Thủy binh). Lúc này giữa hai thành phố Sài Gòn và Chợ Lớn vẫn còn là vùng đầm lầy rộng lớn, chỉ có hai tuyến đường bộ nhỏ hẹp kết nối hai địa phương là route haute de Saigon à Cholon (đường Sài Gòn – Chợ Lớn trên, vốn là con đường cái quan có từ thời Nguyễn, nay là đường Nguyễn Trãi) và route basse de Saigon à Cholon (đường Sài Gòn – Chợ Lớn dưới, con đường chạy dọc theo rạch Bến Nghé, nay thuộc đại lộ Võ Văn Kiệt).[3][4] Năm 1904, thị trưởng Chợ Lớn đề xuất kéo dài đại lộ Bonard của Sài Gòn (đường Lê Lợi ngày nay) đến đường Thủy binh, tuy nhiên đề xuất lúc thì được Hội đồng thành phố Sài Gòn đồng tình, lúc thì không.[5][6]

Sau nhiều năm thảo luận, vào ngày 27 tháng 7 năm 1910 chính quyền đã thông qua dự án với kinh phí lên đến 1,25 triệu piastre, bao gồm cải tạo khu vực đầm lầy Boresse, xây dựng nhà ga xe lửa mới và mở đại lộ nối hai thành phố Sài Gòn và Chợ Lớn. Công trình cơ bản hoàn thiện vào cuối năm 1912.[7] Đến năm 1916, đại lộ Sài Gòn – Chợ Lớn chính thức được đặt tên là đại lộ Galliéni.[8] Ban đầu, đường chỉ trải đất đỏ, đến năm 1928 mới được chỉnh trang, rải đá granit và trải nhựa, bề rộng mặt đường khoảng 20 m.[6][9] Ngoài ra, cũng trong năm này chính quyền đã đưa vào sử dụng tuyến xe điện chạy dọc theo đại lộ.[lower-alpha 1][5][10]

Năm 1955, chính quyền Việt Nam Cộng hòa đổi tên đại lộ Galliéni thành đại lộ Trần Hưng Đạo, đường Thủy binh thành đường Đồng Khánh. Sau năm 1975, Chính phủ Cách mạng lâm thời nhập hai con đường thành đường Trần Hưng Đạo như hiện nay. Tuy nhiên, do địa chỉ nhà trên tuyến đường vẫn giữ nguyên số nhà của hai đường Trần Hưng Đạo và Đồng Khánh trước kia nên đoạn đường Đồng Khánh cũ thường được gọi là "Trần Hưng Đạo B" để phân biệt.[11]